2020 Algorithm                     < No.5  Oil Search>                   Prof. Zoh Q.

2022 Algorithm                       < No.8 Quasi Substring>             Prof. Zoh Q.

준(Quasi)문자열

[문제]   문자열(string) S의 부문자열(substring)은 이 문자열의 특정 구간의 연속된 문자열의 일부를 의미한다. Python의 방식으로 설명하면 문자열 S의 부문자열은 S[i:j]로 표현된다. 부문자열은 부순서(Subsequence)와는 달리 부문자열의 두 문자는 원 문자열에서 반드시 인전해야 한다. 예를 들어 S=algorithms 일 때 부문자열의 예는 아래와 같다. (전부 다는 아님.)

{ algo,  ori, thms, t, al, algorithms, rithms... }

그런데 부문자열의 조건을 약간 느슨하게 하면 좀 더 많은 문제에 응용할 수 있다. 부문자열의 각 문자가 원 문자열에서 반드시 인접해야 한다는 조건을 풀어 한 칸까지 떨어질 수 있다고 하자. 이런 문자열을 준부문자열(Quasi SubString), 간단히 준문자열이라고 부른다. 예를 들어 위 S의 경우 가능한 준문자열의 예는 다음과 같다. 당연히 모든 부문자열(substring)은 준문자열에 포함된다.

{ algri, agrithm, orit, tms, gorthm, rths... }

준문자열은 S의 한 위치에서 시작하여 다음 칸, 혹은 1칸 jump을 하여 선택되는 문자들의 합으로 만들어진다. 준문자열 Q의 인접한 두 문자  [eqn: Q_i]와 [eqn: Q_{i+1]의 경우 만일 [eqn: Q_i = S_k]라고 한다면 [eqn: Q_{i+1 }]은 { [eqn: S _{k+1} ``,``S _{k+2`}] } 이것만 가능하다.

우리는 두 문자열에 존재하는 가장 긴 준문자열(Longest Common Quasi Substring, LCQS)를  찾으려고 한다. 이 문제는 다음에 활용할 수 있다. 만일 어떤 사람이 다른 사람의 text(문자열)을 copy하여 자신의 보고서에 사용한다고 하자. 만일 그대로 베끼면 쉽게 들통이 나기 때문에 베끼는 사람은 복사한 문자열의 중간에 약간의 “잡음”문자를 넣거나 또는 특정 문자를 삭제하는 방식으로 베낀 사실을 감추려고 한다. 예를 들어 아래 두 문자열에서 공통 부문자열은 짧지만 공통 준문자열은 충분히 길어서 두 문자열이 “아주 유사하다”는 것을 알 수 있다.

이런 경우 한 문자열 T는 원래 문자열 S를 거의 베낀 것이라는 것을 확인할 수 있다.

위 두 문자열에서 가장 긴 공통 준문자열 wcomputer_internet_sytm 의 구성을 보자. 그림에서 문자 ‘[eqn: SQCUP]’는 공백(blank)의 의미한다. 입력에서 이 공백문자는 underbar `_'로 표현된다. 당연히 공백문자도 준문자열에 포함된다. 위 그림에서 빨간색 곡선 화살은 jump sequence를 보여준다.

[입출력]   입출력은 모두 stdin과 stdout이다. 입력 파일의 첫 2개의 줄에 문자열 S와 T가 각각 주어진다. 문자열은 모두 영문 소문자와 공백을 의미하는 underbar로만 이루어져 있다. 입력 문자열의 길이 L의 범위는 [eqn: 10` LEQ `L` LEQ `100] 이다. 여러분은 가장 긴 준문자열(Longest Common Quasi Substring)을 찾아서 그 문자열을 출력해야 한다.

만일 그러한 준문자열이 하나 이상일 경우에는 사전식으로 가장 빠른 하나를 찾아서 출력해야 한다.

이 문자열 자체를 추적해서 찾아내는 작업, 요게 약간 까다로울 수가 있다. 특정 구간에서 가장 길면서 사전식으로 제일 빠른 준문자열을 어딘가에 저장해두어야 한다.

stdin	stdout
goodbanana_box cob_aonwanxabin	bananab
abcdefghijk kjihgfedcba	a
comoommoococ comccmccmcccoc	coc

[제한조건] 프로그램 이름은 quasi.{c,cpp,py, java}이다. 제출은 20까지 가능하며 최대 허용 수행시간은 ESPA에서 2초이며 이는 언어에 상관없이 모두 동일하다.

일반적으로 “콰지”, “쿼지”라고 읽는다. 수학에서 흔히 등장하는 용어이기도 하다.